package search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @description: 二分查找（数组必须有序）
 * @title: DichotomySearch
 * @author: zp
 * @date: 2021/11/25 20:50
 */
public class DichotomySearch {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 2, 2, 2);
        System.out.println(search2(list, 0, list.size() - 1, 9));
    }

    public static int search(List<Integer> list, int left, int right, int findValue) {
        if (left > right || list.get(left) > findValue || list.get(right) < findValue) {
            return -1;
        }
        if (left == 0 && right == list.size() - 1) {
            Collections.sort(list);
        }
        //如果使用差值算法优化mid的位置 那公式变成
        //自适应的mid 数值 int mid=left+((findValue-list.get(left))/(list.get(right)-list.get(left)))*(right-left);
        int mid = (right + left) / 2;
        int value = list.get(mid);
        if (findValue > value) {
            return search(list, mid + 1, right, findValue);
        } else if (findValue < value) {
            return search(list, left, mid - 1, findValue);
        } else {
            return mid;
        }
    }

    public static List<Integer> search2(List<Integer> list, int left, int right, int findValue) {
        if (left > right) {
            return new ArrayList<>();
        }
        if (left == 0 && right == list.size() - 1) {
            Collections.sort(list);
        }
        int mid = (right + left) / 2;
        int value = list.get(mid);
        if (findValue > value) {
            return search2(list, mid + 1, right, findValue);
        } else if (findValue < value) {
            return search2(list, left, mid - 1, findValue);
        } else {
            List<Integer> indexList = new ArrayList<>();
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || list.get(temp) != findValue) {
                    break;
                }
                indexList.add(temp);
                temp--;
            }
            indexList.add(mid);
            temp = mid + 1;
            while (temp <= list.size() - 1 && list.get(temp) == findValue) {
                indexList.add(temp);
                temp++;
            }
            return indexList;
        }
    }
}
